---
id: 5900f3cc1000cf542c50fedf
title: 'Problem 96: Sudoku'
challengeType: 1
forumTopicId: 302213
dashedName: problem-96-su-doku
---

# --description--

Sudoku (japanisch für *Zahlenort*) ist die Bezeichnung für ein beliebtes Rätsel. Sein Ursprung ist unklar, aber man sollte ihn Leonhard Euler zuschreiben, der ein ähnliches, aber viel schwierigeres Rätsel namens Lateinische Quadrate erfunden hat. Das Ziel von Sudoku-Rätseln ist es jedoch, die Leerstellen (oder Nullen) in einem 9 x 9-Gitter so zu ersetzen, dass jede Zeile, jede Spalte und jedes 3 x 3-Feld jede der Ziffern 1 bis 9 enthält. Unten siehst du ein Beispiel für ein typisches Start- und Lösungsraster.

<div style="margin: auto; background-color: white; padding: 10px; width: 80%; text-align: center;">
  <table border="0" cellpadding="0" cellspacing="0" align="center">
    <tbody>
      <tr>
        <td>
          <table cellpadding="5" cellspacing="0" border="1">
            <tbody>
              <tr>
                <td style="font-family:'courier new';font-size:14pt; color: black; padding: 5px; border: 2px solid black;">
                  0 0 3<br />9 0 0<br />0 0 1
                </td>
                <td style="font-family:'courier new';font-size:14pt; color: black; padding: 5px; border: 2px solid black;">
                  0 2 0<br />3 0 5<br />8 0 6
                </td>
                <td style="font-family:'courier new';font-size:14pt; color: black; padding: 5px; border: 2px solid black;">
                  6 0 0<br />0 0 1<br />4 0 0
                </td>
              </tr>
              <tr>
                <td style="font-family:'courier new';font-size:14pt; color: black; padding: 5px; border: 2px solid black;">
                  0 0 8<br />7 0 0<br />0 0 6
                </td>
                <td style="font-family:'courier new';font-size:14pt; color: black; padding: 5px; border: 2px solid black;">
                  1 0 2<br />0 0 0<br />7 0 8
                </td>
                <td style="font-family:'courier new';font-size:14pt; color: black; padding: 5px; border: 2px solid black;">
                  9 0 0<br />0 0 8<br />2 0 0
                </td>
              </tr>
              <tr>
                <td style="font-family:'courier new';font-size:14pt; color: black; padding: 5px; border: 2px solid black;">
                  0 0 2<br />8 0 0<br />0 0 5
                </td>
                <td style="font-family:'courier new';font-size:14pt; color: black; padding: 5px; border: 2px solid black;">
                  6 0 9<br />2 0 3<br />0 1 0
                </td>
                <td style="font-family:'courier new';font-size:14pt; color: black; padding: 5px; border: 2px solid black;">
                  5 0 0<br />0 0 9<br />3 0 0
                </td>
              </tr>
            </tbody>
          </table>
        </td>
        <td width="50">
          <img src="images/spacer.gif" width="50" height="1" alt="" /><br />
        </td>
        <td>
          <table cellpadding="5" cellspacing="0" border="1">
            <tbody>
              <tr>
                <td style="font-family:'courier new';font-size:14pt; color: black; padding: 5px; border: 2px solid black;">
                  4 8 3<br />9 6 7<br />2 5 1
                </td>
                <td style="font-family:'courier new';font-size:14pt; color: black; padding: 5px; border: 2px solid black;">
                  9 2 1<br />3 4 5<br />8 7 6
                </td>
                <td style="font-family:'courier new';font-size:14pt; color: black; padding: 5px; border: 2px solid black;">
                  6 5 7<br />8 2 1<br />4 9 3
                </td>
              </tr>
              <tr>
                <td style="font-family:'courier new';font-size:14pt; color: black; padding: 5px; border: 2px solid black;">
                  5 4 8<br />7 2 9<br />1 3 6
                </td>
                <td style="font-family:'courier new';font-size:14pt; color: black; padding: 5px; border: 2px solid black;">
                  1 3 2<br />5 6 4<br />7 9 8
                </td>
                <td style="font-family:'courier new';font-size:14pt; color: black; padding: 5px; border: 2px solid black;">
                  9 7 6<br />1 3 8<br />2 4 5
                </td>
              </tr>
              <tr>
                <td style="font-family:'courier new';font-size:14pt; color: black; padding: 5px; border: 2px solid black;">
                  3 7 2<br />8 1 4<br />6 9 5
                </td>
                <td style="font-family:'courier new';font-size:14pt; color: black; padding: 5px; border: 2px solid black;">
                  6 8 9<br />2 5 3<br />4 1 7
                </td>
                <td style="font-family:'courier new';font-size:14pt; color: black; padding: 5px; border: 2px solid black;">
                  5 1 4<br />7 6 9<br />3 8 2
                </td>
              </tr>
            </tbody>
          </table>
        </td>
      </tr>
    </tbody>
  </table>
</div>

Ein gut konstruiertes Sudoku Rätsel hat eine eindeutige Lösung und kann mit Logik gelöst werden, auch wenn es notwendig sein kann, die „Raten und Testen"-Methoden anzuwenden, um Optionen auszuschließen (darüber gibt es viele kontroverse Meinungen). Die Komplexität der Suche bestimmt die Schwierigkeit des Puzzles; das obige Beispiel wird als einfach angesehen, da es durch direkte Schlussfolgerung gelöst werden kann.

The `puzzlesArr` array contains different Su Doku puzzle strings ranging in difficulty, but all with unique solutions.

Indem du alle Aufgaben in `puzzlesArr` löst, finde die Summe der dreistelligen Zahlen, die du in der linken oberen Ecke jedes Lösungsrasters finden kannst; zum Beispiel 483 ist die 3-stellige Nummer in der oberen linken Ecke des oben zu sehenden Lösungsrasters.

# --hints--

`suDoku(testPuzzles1)` sollte eine Zahl zurückgeben.

```js
assert(typeof suDoku(_testPuzzles1) === 'number');
```

`suDoku(testPuzzles1)` sollte `1190` zurückgeben.

```js
assert.strictEqual(suDoku(_testPuzzles1), 1190);
```

`suDoku(testPuzzles2)` sollte `24702` zurückgeben.

```js
assert.strictEqual(suDoku(_testPuzzles2), 24702);
```

# --seed--

## --after-user-code--

```js
const _testPuzzles1 = [
  '003020600900305001001806400008102900700000008006708200002609500800203009005010300',
  '200080300060070084030500209000105408000000000402706000301007040720040060004010003',
  '000000907000420180000705026100904000050000040000507009920108000034059000507000000'
];

const _testPuzzles2 = [
  '003020600900305001001806400008102900700000008006708200002609500800203009005010300',
  '200080300060070084030500209000105408000000000402706000301007040720040060004010003',
  '000000907000420180000705026100904000050000040000507009920108000034059000507000000',
  '030050040008010500460000012070502080000603000040109030250000098001020600080060020',
  '020810740700003100090002805009040087400208003160030200302700060005600008076051090',
  '100920000524010000000000070050008102000000000402700090060000000000030945000071006',
  '043080250600000000000001094900004070000608000010200003820500000000000005034090710',
  '480006902002008001900370060840010200003704100001060049020085007700900600609200018',
  '000900002050123400030000160908000000070000090000000205091000050007439020400007000',
  '001900003900700160030005007050000009004302600200000070600100030042007006500006800',
  '000125400008400000420800000030000095060902010510000060000003049000007200001298000',
  '062340750100005600570000040000094800400000006005830000030000091006400007059083260',
  '300000000005009000200504000020000700160000058704310600000890100000067080000005437',
  '630000000000500008005674000000020000003401020000000345000007004080300902947100080',
  '000020040008035000000070602031046970200000000000501203049000730000000010800004000',
  '361025900080960010400000057008000471000603000259000800740000005020018060005470329',
  '050807020600010090702540006070020301504000908103080070900076205060090003080103040',
  '080005000000003457000070809060400903007010500408007020901020000842300000000100080',
  '003502900000040000106000305900251008070408030800763001308000104000020000005104800',
  '000000000009805100051907420290401065000000000140508093026709580005103600000000000',
  '020030090000907000900208005004806500607000208003102900800605007000309000030020050',
  '005000006070009020000500107804150000000803000000092805907006000030400010200000600',
  '040000050001943600009000300600050002103000506800020007005000200002436700030000040',
  '004000000000030002390700080400009001209801307600200008010008053900040000000000800',
  '360020089000361000000000000803000602400603007607000108000000000000418000970030014',
  '500400060009000800640020000000001008208000501700500000000090084003000600060003002',
  '007256400400000005010030060000508000008060200000107000030070090200000004006312700',
  '000000000079050180800000007007306800450708096003502700700000005016030420000000000',
  '030000080009000500007509200700105008020090030900402001004207100002000800070000090',
  '200170603050000100000006079000040700000801000009050000310400000005000060906037002',
  '000000080800701040040020030374000900000030000005000321010060050050802006080000000',
  '000000085000210009960080100500800016000000000890006007009070052300054000480000000',
  '608070502050608070002000300500090006040302050800050003005000200010704090409060701',
  '050010040107000602000905000208030501040070020901080406000401000304000709020060010',
  '053000790009753400100000002090080010000907000080030070500000003007641200061000940',
  '006080300049070250000405000600317004007000800100826009000702000075040190003090600',
  '005080700700204005320000084060105040008000500070803010450000091600508007003010600',
  '000900800128006400070800060800430007500000009600079008090004010003600284001007000',
  '000080000270000054095000810009806400020403060006905100017000620460000038000090000',
  '000602000400050001085010620038206710000000000019407350026040530900020007000809000',
  '000900002050123400030000160908000000070000090000000205091000050007439020400007000',
  '380000000000400785009020300060090000800302009000040070001070500495006000000000092',
  '000158000002060800030000040027030510000000000046080790050000080004070100000325000',
  '010500200900001000002008030500030007008000500600080004040100700000700006003004050',
  '080000040000469000400000007005904600070608030008502100900000005000781000060000010',
  '904200007010000000000706500000800090020904060040002000001607000000000030300005702',
  '000700800006000031040002000024070000010030080000060290000800070860000500002006000',
  '001007090590080001030000080000005800050060020004100000080000030100020079020700400',
  '000003017015009008060000000100007000009000200000500004000000020500600340340200000',
  '300200000000107000706030500070009080900020004010800050009040301000702000000008006'
];
```

## --seed-contents--

```js
function suDoku(puzzlesArr) {

  return true;
}

// Only change code above this line

const testPuzzles1 = [
  '003020600900305001001806400008102900700000008006708200002609500800203009005010300',
  '200080300060070084030500209000105408000000000402706000301007040720040060004010003',
  '000000907000420180000705026100904000050000040000507009920108000034059000507000000'
];

suDoku(testPuzzles1);
```

# --solutions--

```js
function suDoku(puzzlesArr) {
  function solve(puzzle) {
    for (let row = 0; row < 9; row++) {
      for (let col = 0; col < 9; col++) {
        if (puzzle[row][col] > 0) {
          continue;
        }

        const allowedNumbers = getAllowedNumbers(puzzle, row, col);

        for (let number = 1; number <= 9; number++) {
          if (allowedNumbers[number]) {
            puzzle[row][col] = number;
            if (solve(puzzle)) {
              return true;
            }
          }
        }

        puzzle[row][col] = 0;
        return false;
      }
    }
    return true;
  }

  function getAllowedNumbers(puzzle, row, col) {
    const allowed = new Array(10).fill(true);
    allowed[0] = false;

    for (let i = 0; i < 9; i++) {
      const numberInSameRow = puzzle[row][i];
      if (numberInSameRow > 0) {
        allowed[numberInSameRow] = false;
      }

      const numberInSameCol = puzzle[i][col];
      if (numberInSameCol > 0) {
        allowed[numberInSameCol] = false;
      }
    }

    const rowOfSubGrid = Math.floor(row / 3) * 3;
    const colOfSubGrid = Math.floor(col / 3) * 3;
    for (let rowInSubGrid = 0; rowInSubGrid < 3; rowInSubGrid++) {
      for (let colInSubGrid = 0; colInSubGrid < 3; colInSubGrid++) {
        const numberInSameSubGrid =
          puzzle[rowOfSubGrid + rowInSubGrid][colOfSubGrid + colInSubGrid];
        if (numberInSameSubGrid > 0) {
          allowed[numberInSameSubGrid] = false;
        }
      }
    }

    return allowed;
  }

  function parsePuzzle(string) {
    const puzzle = [];
    for (let row = 0; row < 9; row++) {
      puzzle.push(
        string
          .slice(row * 9, 9 + row * 9)
          .split('')
          .map(x => parseInt(x, 10))
      );
    }
    return puzzle;
  }

  let sum = 0;
  for (let i = 0; i < puzzlesArr.length; i++) {
    const puzzle = parsePuzzle(puzzlesArr[i]);
    if (solve(puzzle)) {
      sum += 100 * puzzle[0][0] + 10 * puzzle[0][1] + puzzle[0][2];
    }
  }

  return sum;
}
```
